package wtx.leetcode;

class MaxProfit {
  // 用分治算法试一下
  public int maxProfit(int[] prices) {
    if (prices == null || prices.length < 2) {
      return 0;
    }
    return maxProfit_(prices, 0, prices.length);
  }

  int maxProfit_(int[] prices, int left, int right) {
    if (right - left <= 3) {
      int maxv = 0;
      int minv = Integer.MAX_VALUE;
      int maxp = 0;
      for (int i = left; i < right; ++i) {
        if (prices[i] > maxv) {
          maxv = prices[i];
        }
        if (prices[i] < minv) {
          minv = prices[i];
        }
        for (int j = i+1; j < right; ++j) {
          if (prices[j]-prices[i] > maxp) {
            maxp = prices[j] - prices[i];
          }
        }
      }
      prices[left] = minv;
      prices[right-1] = maxv;
      return maxp;
    }
    assert (right - left >= 2);
    int mid = (left + right)/2;
    int m1 = maxProfit_(prices, left, mid);
    int m2 = maxProfit_(prices, mid, right);
    int m3 = prices[right - 1] - prices[left];
    prices[left] = Math.min(prices[left], prices[mid]);
    prices[right-1] = Math.max(prices[mid-1], prices[right-1]);
    return Math.max(m1, Math.max(m2, m3));
  }
}